<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<title>Algorithm</title>
<link rel="stylesheet" href="../../../../../doc/src/boostbook.css" type="text/css">
<meta name="generator" content="DocBook XSL Stylesheets V1.79.1">
<link rel="home" href="../index.html" title="Chapter 1. Fusion 2.2">
<link rel="up" href="../index.html" title="Chapter 1. Fusion 2.2">
<link rel="prev" href="adapted/define_assoc_tpl_struct.html" title="BOOST_FUSION_DEFINE_ASSOC_TPL_STRUCT">
<link rel="next" href="algorithm/auxiliary.html" title="Auxiliary">
</head>
<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF">
<table cellpadding="2" width="100%"><tr>
<td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../../../boost.png"></td>
<td align="center"><a href="../../../../../index.html">Home</a></td>
<td align="center"><a href="../../../../../libs/libraries.htm">Libraries</a></td>
<td align="center"><a href="http://www.boost.org/users/people.html">People</a></td>
<td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td>
<td align="center"><a href="../../../../../more/index.htm">More</a></td>
</tr></table>
<hr>
<div class="spirit-nav">
<a accesskey="p" href="adapted/define_assoc_tpl_struct.html"><img src="../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../index.html"><img src="../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="algorithm/auxiliary.html"><img src="../../../../../doc/src/images/next.png" alt="Next"></a>
</div>
<div class="section">
<div class="titlepage"><div><div><h2 class="title" style="clear: both">
<a name="fusion.algorithm"></a><a class="link" href="algorithm.html" title="Algorithm">Algorithm</a>
</h2></div></div></div>
<div class="toc"><dl class="toc">
<dt><span class="section"><a href="algorithm/auxiliary.html">Auxiliary</a></span></dt>
<dd><dl>
<dt><span class="section"><a href="algorithm/auxiliary/functions.html">Functions</a></span></dt>
<dt><span class="section"><a href="algorithm/auxiliary/metafunctions.html">Metafunctions</a></span></dt>
</dl></dd>
<dt><span class="section"><a href="algorithm/iteration.html">Iteration</a></span></dt>
<dd><dl>
<dt><span class="section"><a href="algorithm/iteration/functions.html">Functions</a></span></dt>
<dt><span class="section"><a href="algorithm/iteration/metafunctions.html">Metafunctions</a></span></dt>
</dl></dd>
<dt><span class="section"><a href="algorithm/query.html">Query</a></span></dt>
<dd><dl>
<dt><span class="section"><a href="algorithm/query/functions.html">Functions</a></span></dt>
<dt><span class="section"><a href="algorithm/query/metafunctions.html">Metafunctions</a></span></dt>
</dl></dd>
<dt><span class="section"><a href="algorithm/transformation.html">Transformation</a></span></dt>
<dd><dl>
<dt><span class="section"><a href="algorithm/transformation/functions.html">Functions</a></span></dt>
<dt><span class="section"><a href="algorithm/transformation/metafunctions.html">Metafunctions</a></span></dt>
</dl></dd>
</dl></div>
<h4>
<a name="fusion.algorithm.h0"></a>
      <span class="phrase"><a name="fusion.algorithm.lazy_evaluation"></a></span><a class="link" href="algorithm.html#fusion.algorithm.lazy_evaluation">Lazy
      Evaluation</a>
    </h4>
<p>
      Unlike <a href="http://www.boost.org/libs/mpl" target="_top">MPL</a>, Fusion algorithms
      are lazy<a href="#ftn.fusion.algorithm.f0" class="footnote" name="fusion.algorithm.f0"><sup class="footnote">[12]</sup></a> and non sequence-type preserving <a href="#ftn.fusion.algorithm.f1" class="footnote" name="fusion.algorithm.f1"><sup class="footnote">[13]</sup></a>. This is by design. Runtime efficiency is given a high priority.
      Like <a href="http://www.boost.org/libs/mpl" target="_top">MPL</a>, and unlike <a href="http://en.wikipedia.org/wiki/Standard_Template_Library" target="_top">STL</a>, fusion
      algorithms are mostly functional in nature such that algorithms are non mutating
      (no side effects). However, due to the high cost of returning full sequences
      such as vectors and lists, <span class="emphasis"><em>Views</em></span> are returned from Fusion
      algorithms instead. For example, the <a class="link" href="algorithm/transformation/functions/transform.html" title="transform"><code class="computeroutput"><span class="identifier">transform</span></code></a> algorithm does not actually
      return a transformed version of the original sequence. <a class="link" href="algorithm/transformation/functions/transform.html" title="transform"><code class="computeroutput"><span class="identifier">transform</span></code></a> returns a <a class="link" href="view/transform_view.html" title="transform_view"><code class="computeroutput"><span class="identifier">transform_view</span></code></a>. This view holds a
      reference to the original sequence plus the transform function. Iteration over
      the <a class="link" href="view/transform_view.html" title="transform_view"><code class="computeroutput"><span class="identifier">transform_view</span></code></a>
      will apply the transform function over the sequence elements on demand. This
      <span class="emphasis"><em>lazy</em></span> evaluation scheme allows us to chain as many algorithms
      as we want without incurring a high runtime penalty.
    </p>
<h4>
<a name="fusion.algorithm.h1"></a>
      <span class="phrase"><a name="fusion.algorithm.sequence_extension"></a></span><a class="link" href="algorithm.html#fusion.algorithm.sequence_extension">Sequence
      Extension</a>
    </h4>
<p>
      The <span class="emphasis"><em>lazy</em></span> evaluation scheme where <a class="link" href="algorithm.html" title="Algorithm">Algorithms</a>
      return <a class="link" href="view.html" title="View">Views</a> also allows operations such
      as <a class="link" href="algorithm/transformation/functions/push_back.html" title="push_back"><code class="computeroutput"><span class="identifier">push_back</span></code></a> to be totally generic. In
      Fusion, <a class="link" href="algorithm/transformation/functions/push_back.html" title="push_back"><code class="computeroutput"><span class="identifier">push_back</span></code></a> is actually a generic algorithm
      that works on all sequences. Given an input sequence <code class="computeroutput"><span class="identifier">s</span></code>
      and a value <code class="computeroutput"><span class="identifier">x</span></code>, Fusion's <a class="link" href="algorithm/transformation/functions/push_back.html" title="push_back"><code class="computeroutput"><span class="identifier">push_back</span></code></a> algorithm simply returns
      a <a class="link" href="view/joint_view.html" title="joint_view"><code class="computeroutput"><span class="identifier">joint_view</span></code></a>:
      a view that holds a reference to the original sequence <code class="computeroutput"><span class="identifier">s</span></code>
      and the value <code class="computeroutput"><span class="identifier">x</span></code>. Functions
      that were once sequence specific and need to be implemented N times over N
      different sequences are now implemented only once. That is to say that Fusion
      sequences are cheaply extensible.
    </p>
<p>
      To regain the original sequence, <a class="link" href="container/conversion/functions.html" title="Functions">Conversion</a>
      functions are provided. You may use one of the <a class="link" href="container/conversion/functions.html" title="Functions">Conversion</a>
      functions to convert back to the original sequence type.
    </p>
<h4>
<a name="fusion.algorithm.h2"></a>
      <span class="phrase"><a name="fusion.algorithm.header"></a></span><a class="link" href="algorithm.html#fusion.algorithm.header">Header</a>
    </h4>
<pre class="programlisting"><span class="preprocessor">#include</span> <span class="special">&lt;</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">fusion</span><span class="special">/</span><span class="identifier">algorithm</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">&gt;</span>
<span class="preprocessor">#include</span> <span class="special">&lt;</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">fusion</span><span class="special">/</span><span class="identifier">include</span><span class="special">/</span><span class="identifier">algorithm</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">&gt;</span>
</pre>
<div class="footnotes">
<br><hr style="width:100; text-align:left;margin-left: 0">
<div id="ftn.fusion.algorithm.f0" class="footnote"><p><a href="#fusion.algorithm.f0" class="para"><sup class="para">[12] </sup></a>
        Except for some special cases such as <a class="link" href="algorithm/iteration/functions/for_each.html" title="for_each"><code class="computeroutput"><span class="identifier">for_each</span></code></a> and <a class="link" href="algorithm/auxiliary/functions/copy.html" title="copy"><code class="computeroutput"><span class="identifier">copy</span></code></a> which are inherently imperative
        algorithms.
      </p></div>
<div id="ftn.fusion.algorithm.f1" class="footnote"><p><a href="#fusion.algorithm.f1" class="para"><sup class="para">[13] </sup></a>
        What does that mean? It means that when you operate on a sequence through
        a Fusion algorithm that returns a sequence, the sequence returned may not
        be of the same class as the original
      </p></div>
</div>
</div>
<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
<td align="left"></td>
<td align="right"><div class="copyright-footer">Copyright © 2001-2006, 2011, 2012 Joel de Guzman,
      Dan Marsden, Tobias Schwinger<p>
        Distributed under the Boost Software License, Version 1.0. (See accompanying
        file LICENSE_1_0.txt or copy at <a href="http://www.boost.org/LICENSE_1_0.txt" target="_top">http://www.boost.org/LICENSE_1_0.txt</a>)
      </p>
</div></td>
</tr></table>
<hr>
<div class="spirit-nav">
<a accesskey="p" href="adapted/define_assoc_tpl_struct.html"><img src="../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../index.html"><img src="../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="algorithm/auxiliary.html"><img src="../../../../../doc/src/images/next.png" alt="Next"></a>
</div>
</body>
</html>
